package a02_链表;

/**
 * @author: fosss
 * Date: 2023/7/22
 * Time: 21:27
 * Description:
 * leetcode位置：https://leetcode.cn/problems/linked-list-cycle-ii/
 * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 * 为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
 * 说明：不允许修改给定的链表。
 */
public class B07_找链表的环出现的结点 {
    /**
     * 双指针法，参考https://leetcode.cn/problems/linked-list-cycle-ii/solution/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/
     */
    public ListNode f(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        //fast每次走两步，slow每次走一步
        while (true) {
            if (fast == null || fast.next == null) {
                //走到头了，没有环
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        //此时到达快慢指针第一次相交的位置，快指针放到head位置，然后同时一步一步走，知道快慢指针再相交即为环入口。具体原因看参考中的推导
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;

    }
}














